package J.算法.回溯算法;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class _77组合 {

    List<Integer> list = new LinkedList<>();
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {

        backTracking(n,k,1);
        return res;

    }

    void backTracking(int n,int k,int start){
        int size = list.size();
        // 剪枝操作
        if (k - size > n - start + 1) {
            return;
        }

        if (list.size() == k){
            res.add(new LinkedList(list));
            return;
        }

        for (int i = start; i <= n; i++) {
            list.add(i);
            backTracking(n,k,i+1);
            list.remove(list.size()-1);
            
        }
    }
}
